/**
 * 
 */
package de.gee.erep.shared.utils.sort;

import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;

/**
 * @author Matthew Gee created: 02.04.2011
 */
public class StandardHeapSort<T extends Comparable<T>> extends Heapsort<T> {
	/***/
	private static final long serialVersionUID = 1L;

	public StandardHeapSort() {
		super();
	}

	@Override
	public T[] sort(T[] toSort) {
		buildMaxHeap(toSort);
		for (int i = toSort.length - 1; i > 0; i--) {
			swap(toSort, 0, i);
			sink(toSort, 0, i - 1);
		}
		return toSort;
	}

	@SuppressWarnings({ "unchecked", "rawtypes" })
	public void sort(List<T> list, Comparator<? super T> c) {
		Object[] a = list.toArray();
		buildMaxHeap(a, c);
		for (int i = a.length - 1; i > 0; i--) {
			swap(a, 0, i);
			sink(a, 0, i - 1, c);
		}
		ListIterator i = list.listIterator();
		for (int j = 0; j < a.length; j++) {
			i.next();
			i.set(a[j]);
		}

	}
}
